//一个简简单单的链表
/**index always begin 0-index*/
#include <stdlib.h>
typedef struct MyLinkedList
{
    int val;
    struct MyLinkedList *next;
} MyLinkedList;

/** Initialize your data structure here. */
MyLinkedList *myLinkedListCreate()
{
    /*
    1. 这里为什么不用 MyLinkedList * node呢
        因为无法指向一个有效的指针地址
    2. 为什么不用MyLinkedList node return &node呢？
        因为无法后续释放内存，或者在返回后node的内存区域会被清理
    */
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->next = NULL;
    return node;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList *obj, int index)
{
    if (index < 0 || obj->next == NULL)
        return -1;
    /* 
    关于操作的obj到底是个啥的问题？
        想一下，obj作为一个MyLinkedList的指针传递进来是一个形式参数，
        若对其进行诸如修改头节点，删除头节点的函数时，obj实际上会修改为
        申请malloc后地址，然后退出
        这时灾难发送了，由于改变的形式参数地址的指向，实参并未修改，同时
        也引发了malloc内存泄漏的问题
    所以需要一个又malloc创建的一个不变的地址管理0-index节点，这就是传递进来的obj   
    */
    MyLinkedList *node = obj;
    for (int i = 0; i <= index; i++)
    {
        if (node->next != NULL)
            node = node->next;
        else
            return -1;
    }
    return node->val;
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void myLinkedListAddAtHead(MyLinkedList *obj, int val)
{
    /*
    添加头节点到原链表
        有了上述的铺垫，这里就好理解和设计了
    */
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    node->next = obj->next;
    obj->next = node;
}
/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList *obj, int val)
{
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    //注意赋值NULL，也可以直接调用create
    node->next = NULL;
    MyLinkedList *temp = obj;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = node;
}

/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(MyLinkedList *obj, int index)
{
    /*
    有几种状态=头节点，中间节点，尾节点
    */
    if (index < 0 || obj->next == NULL)
        return;
    MyLinkedList *node = obj;
    for (int i = 0; i < index; i++)
    {
        if (node->next == NULL)
            return;
        else
            node = node->next;
    }
    if (node->next == NULL)
    {
        return;
    }

    node->next = node->next->next;
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void myLinkedListAddAtIndex(MyLinkedList *obj, int index, int val)
{
    MyLinkedList *node = myLinkedListCreate();
    node->val = val;
    MyLinkedList *temp = obj;
    if (index <= 0)
    {
        node->next = obj->next;
        obj->next = node;
        return;
    }
    int i = 0;
    for (; i < index; i++)
    {
        if (temp->next == NULL)
            break;
        else
            temp = temp->next;
    }
    if (index == i + 1)
    {
        temp->next = node;
    }
    if (index < i + 1)
    {
        node->next = temp->next;
        temp->next = node;
    }
}
void myLinkedListFree(MyLinkedList *obj)
{
    MyLinkedList *node = obj;
    MyLinkedList *tmp;
    while (node)
    {
        tmp = node->next;
        free(node);
        node = tmp;
    }
}
int main()
{
    MyLinkedList *head = myLinkedListCreate();
    myLinkedListAddAtHead(head, 2);
    myLinkedListDeleteAtIndex(head, 1);
    myLinkedListAddAtHead(head, 2);
    myLinkedListAddAtHead(head, 7);
    myLinkedListAddAtHead(head, 3);
    myLinkedListAddAtHead(head, 2);
    myLinkedListAddAtHead(head, 5);
    myLinkedListAddAtTail(head, 5);
    int a = myLinkedListGet(head, 5);
    myLinkedListDeleteAtIndex(head, 6);
    myLinkedListDeleteAtIndex(head, 4);
}